#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def largestRectangleArea(self, heights):
        if not heights:
            return 0

        self.heights = heights

        self.height_stack = []
        self.idx_stack = []

        self.height_stack_push(0)

        l = len(heights)

        max_area = 0

        for idx in range(1, l):
            pre_height = self.height_stack[-1]
            cur_height = self.heights[idx]
            if cur_height >= pre_height:
                self.height_stack_push(idx)
            else:
                print('else %s' % cur_height)
                pop_max = self.height_stack_pop_max(idx, cur_height)
                max_area = max(pop_max, max_area)
                self.height_stack_push(idx)     # 最后一个元素一定会进栈

        max_area = max(
            max_area,
            self.height_stack_pop_max(l, 0)        # 假设最后有一个哨兵位于self.len, 并且val=0
        )

        return max_area

    def height_stack_pop_max(self, cut_idx, cut_value):
        max_area = 0
        print('self.height_stack %s, cur_value %s, idx %s' % (self.height_stack, cut_value, cut_idx) )

        while self.height_stack and self.height_stack[-1] > cut_value:
            height = self.height_stack.pop()
            self.idx_stack.pop()

            # 当前栈顶元素一定比height小于等于, 栈顶索引+1 一定比height大(从左边最先比自己大的第一个到右边比自己小的第一个)
            if self.idx_stack:
                pre_idx = self.idx_stack[-1]
            else:
                pre_idx = -1
            idx = pre_idx + 1

            max_area = max(max_area, height * (cut_idx-idx))
            # print('pop %s' % max_area)

        return max_area

    def height_stack_push(self, idx):
        self.height_stack.append(self.heights[idx])
        self.idx_stack.append(idx)


def main():
    print("start main")
    s = Solution()
    l = [2,1,5,6]
    # l = [2,1,5,6,2,3]
    l = [5,4,1,2]
    ret = s.largestRectangleArea(l)
    print(ret)

if __name__ == "__main__":
    main()
